//
// Created by 86138 on 2025/6/14.
//

#ifndef QINGDAO_UNIVERSITY_BITREE_H
#define QINGDAO_UNIVERSITY_BITREE_H
#include "../01-intro/c1-1.h"

namespace sweetcookie6_1 {
    #define MAX_QSIZE 6

    typedef char TElemType;

    typedef struct BiTNode {
        TElemType data;
        struct BiTNode *lchild, *rchild;
    } BiTNode;

    typedef BiTNode *BiTree;

    // 链栈相关定义和方法 -- 开始
    typedef BiTNode* SElemType;
    typedef struct StackNode {
        SElemType Data;
        struct StackNode *Next;
    } StackNode, *LinkStack;

    void InitLinkStack(LinkStack &S);
    void DestroyLinkStack(LinkStack &S);
    Status Push(LinkStack &S, SElemType e);
    Status Pop(LinkStack &S, SElemType &e);
    bool StackEmpty(LinkStack S);
    // 链栈相关定义和方法 -- 结束

    // 循环顺序队列相关定义和方法 -- 开始
    typedef BiTNode* QElemType;
    typedef struct {
        QElemType* base;
        int front;
        int rear;
    } SqQueue;

    void InitQueue(SqQueue &Q);
    void DestroyQueue(SqQueue &Q);
    bool QueueEmpty(SqQueue Q);
    Status EnQueue(SqQueue &Q, QElemType e);
    Status DeQueue(SqQueue &Q, QElemType &e);
    // 循环顺序队列相关定义和方法 -- 结束

    void InitBiTree(BiTree &T);

    void DestroyBiTree(BiTree &T);

    Status InOrderTraverseNoRecur(BiTree T);

    Status PreOrderTraverseNoRecur(BiTree T);

    Status LevelOrderTraverse(BiTree T);

    void CreateBiTree(BiTree &T, char*& pstr);
}
#endif //QINGDAO_UNIVERSITY_BITREE_H
